package com.leetcode.根据算法进行分类.中值问题相关;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: ZhouBert
 * @date: 2021/2/3
 * @description: 295. 数据流的中位数
 * https://leetcode-cn.com/problems/find-median-from-data-stream/
 * 参考：
 * https://www.baidu.com/link?url=IhnFKIciyydY3ZsVIJm77BDFGTxFUCgR8GA_dvzV1AUEzNE7wp1Sx2nla7RhwMIpLDb5zhqxwsRv0Mx0Jvi9ljjiZBjlJ8wsuw3uDNPHzFe&wd=&eqid=a7a0e2f20000b63500000004601a6cac
 */
public class C_295_数据流的中位数 {

    public static void main(String[] args) {

        MedianFinder medianFinder = new MedianFinder();
        test2(medianFinder);

    }

    public void test1(MedianFinder medianFinder) {
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }

    public static void test2(MedianFinder medianFinder) {
        medianFinder.addNum(-1);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-3);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-4);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(-5);
        System.out.println(medianFinder.findMedian());
    }


    /**
     * 这个可以是解决中值问题的特殊结构了
     * 使用一个小顶堆+一个大顶堆 来实现O(logN )级别的中值问题
     */
    static class MedianFinder {

        /**
         * 元素的数量
         */
        int count = 0;
        /**
         * 构建一个小顶堆（将半数大数放入小顶堆）
         */
        PriorityQueue<Integer> smallTopHeap;
        /**
         * 构建一个大顶堆（将半数小数放入小顶堆）
         */
        PriorityQueue<Integer> bigTopHeap;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
            smallTopHeap = new PriorityQueue<>();
            bigTopHeap = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            });
        }

        /**
         * smallTopHeap 的堆顶元素代表大数的最小值；
         * bigTopHeap 的堆顶元素代表小数的最大值
         * 【保证 bigTopHeap 的值永远小于等于 smallTopHeap 的值】
         * --
         * 如果没有元素，先放入 smallTopHeap
         * 如果已经存在元素：
         * 1.判断
         *
         * @param num
         */
        public void addNum(int num) {
            count++;
            //1.没有元素时的处理方式
            if (bigTopHeap.isEmpty() && smallTopHeap.isEmpty()) {
                smallTopHeap.offer(num);
                return;
            }
            //小顶堆的堆顶元素
            Integer value = smallTopHeap.peek();
            if (smallTopHeap.size() > bigTopHeap.size()) {
                //如果 小顶堆的数量大于 大顶堆的数量
                //-> 将元素放到大顶堆，在此之前需要判断该元素是否需要交换
                if (num > value) {
                    //需要跟堆顶交换位置
                    value = smallTopHeap.poll();
                    smallTopHeap.offer(num);
                    bigTopHeap.offer(value);
                }else {
                    bigTopHeap.offer(num);
                }

            } else {
                //如果小顶堆的数量 小于等于 大顶堆的数量 -> 添加到小顶堆
                value = bigTopHeap.peek();
                if (value > num) {
                    //需要交换大顶堆的值
                    value = bigTopHeap.poll();
                    bigTopHeap.offer(num);
                    smallTopHeap.offer(value);
                }else {
                    smallTopHeap.offer(num);
                }

            }
        }

        public double findMedian() {
            if ((count & 1) == 1) {
                //如果是奇数
                //由于定义了小顶堆的数量大于大顶堆
                return smallTopHeap.peek();
            } else {
                //如果是偶数
                return ((double) smallTopHeap.peek() + (double) bigTopHeap.peek()) / 2;
            }
        }
    }
}
